import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class SubstringWithConcatenationOfAllWords {
    // 找到字符串中所有字母异位词的变题(从找单个字符变成字符串,但把字符串看作是一个整体即可)
    // 前提: 把 字符串 看作是一个整体
    // 规则: 窗口固定大小为 words 的长度, 且窗口内字符串内容与 words 中的是相同的(顺序没有要求)
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> list = new ArrayList<>();
        // key-字符串   value-字符串出现的次数
        Map<String, Integer> hash2 = new HashMap<>();
        for(String x : words) {
            hash2.put(x, hash2.getOrDefault(x, 0) + 1);
        }

        int n = s.length();
        int wordLen = words[0].length(); // 要比较的轮次, 同时也是每次进窗口的字符的个数
        int tmp = 0;
        int windowSize = words.length; // 窗口大小
        while(tmp != wordLen) {
            Map<String, Integer> hash1 = new HashMap<>();
            int left = tmp, right = tmp;
            int count = 0; // 有效字符串的个数
            while(right + wordLen <= n) {
                // 1.进窗口
                String in = s.substring(right, right += wordLen);
                hash1.put(in, hash1.getOrDefault(in, 0) + 1);
                if(hash1.get(in).compareTo(hash2.getOrDefault(in, 0)) <= 0) {
                    count++;
                }

                // 判断是否要出窗口以及更新结果
                while((right - left) / wordLen == windowSize) {
                    if(count == windowSize) {
                        // 满足条件, 更新结果
                        list.add(left);
                    }

                    // 2.出窗口
                    String out = s.substring(left, left += wordLen);
                    hash1.put(out, hash1.get(out) - 1);
                    if(hash1.get(out).compareTo(hash2.getOrDefault(out, 0)) < 0) {
                        count--;
                    }
                }
            }
            tmp++;
        }
        return list;
    }
}
